#ifndef __QUEUE_H__
#define __QUEUE_H__


/*
    |    ===========================================================    |
    |    This Queue Class has been implemented with templates and       |
    |    the size is determined dynamically at initialization.               |
    |                                                                                               |
    |    The actual amount of space allocated for the Queue will be     |
    |    one more element space than the defined maximum size. This     |
    |    is useful for implementing the Queue in a circular method.     |
    |                                                                                          |
    |    To understand the circular implementation, think of the        |
    |    array as a circle. When you reach the end of the array, you    |
    |    wrap around to the beginning of the array.                     |
    |                                                                   |
    |    So, when an element is dequeued, the Queue doesn't shift.      |
    |    Instead, you updated an indicator of the start of the queue.   |
    |                                                                   |
     -------------------------------------------------------------------
*/

#include <assert.h>

template <class Elem>
class Queue 
{
public:
	Queue(int maxSize = 500);
	Queue(const Queue<Elem> &otherQueue);
	~Queue(void);
	void enQueue(const Elem& item); // add elem to queue
	Elem deQueue(void);                     //remove elem from queue
	int size(void); // elem number of queue

private:
	Elem *m_data;            // The actual Data array
	const int MAX_QUEUE_SIZE; // The actual spaces will be one more than this
	int m_begin;              // Numbered location of the start and end
	int m_end;
	int m_ElemCount;
};

template <class Elem>
Queue<Elem>::Queue(int maxSize):MAX_QUEUE_SIZE(maxSize)
{
	m_data = new Elem[maxSize + 1];
	m_begin = 0;
	m_end = 0;
	m_ElemCount = 0;
}

template <class Elem>
Queue<Elem>::Queue(const Queue<Elem> &otherQueue):
				MAX_QUEUE_SIZE(otherQueue.MAX_QUEUE_SIZE)
{
	m_begin = otherQueue.m_begin;
	m_end = otherQueue.m_end;
	m_ElemCount = otherQueue.m_ElemCount;

	m_data = new Elem[MAX_QUEUE_SIZE];
	for(int i = 0; i < MAX_QUEUE_SIZE; i++)
		m_data[i] = otherQueue.m_data[i];
}

template <class Elem>
Queue<Elem>::~Queue()
{
	delete[] m_data;
}

template <class Elem>
void Queue<Elem>::enQueue(const Elem& item)
{
	assert(m_ElemCount < MAX_QUEUE_SIZE);

	m_data[m_end++] = item;
	++m_ElemCount;

	if(m_end > MAX_QUEUE_SIZE)
		m_end -= (MAX_QUEUE_SIZE + 1);

}

template <class Elem>
Elem Queue<Elem>::deQueue(void)
{
	assert(m_ElemCount > 0);

	Elem ret = m_data[m_begin++];
	--m_ElemCount;

	if(m_begin > MAX_QUEUE_SIZE)
		m_begin -= MAX_QUEUE_SIZE;

	return ret;
}
				
template <class Elem>
inline int Queue<Elem>::size(void)
{
	return m_ElemCount;
}

#endif  //__QUEUE_H__